//
// Created by 86152 on 2021/5/4.
//

#include "part4.h"
#include <cstring>
#include <iostream>
#include <cmath>
namespace part4{
    void initNext(int* next,const char* pattern){
        int len = strlen(pattern);
        int i = 1;
        int j = 0;

        next[0] = -1;
        next[1] = 0;

        while (i < len){
            if(j == -1 || pattern[i] == pattern[j]){
                next[++i] = ++j;
            }else{
                j = next[j];
            }
        }

    }

    int kmp(const char* str,const char* pattern){
        int len1 = strlen(str);
        int len2 = strlen(pattern);

        int* next = new int[len2+1];
        // len2-1处匹配成功为会在len2处赋值，因此要多申请一块内存

        initNext(next, pattern);

        // 一开始都从0处开始匹配
        int i = 0;
        int j = 0;

        while (i < len1 && j < len2){

            // j == -1,代表第一个字符匹配失败，此时i应该后移，j应该设置为0，j++刚好也为0
            // str[i] == pattern[j] 表示匹配成功，二者都应该后移
            if (j == -1 || str[i] == pattern[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        delete [] next;

        if (j == len2){
            return i - j;
        }
        return -1;
    }


    int page127_5(int i, int j){
        int i_parent = i;
        int j_parent = j;

        // 先求高度
        int i_hight = std::log2(i) + 1;
        int j_hight = std::log2(j) + 1;

        // i高，先让i上升
        if (i_hight > j_hight){
            for (int k = 0; k < i_hight - j_hight; ++k) {
                i_parent = i_parent / 2;
            }
        } else if (i_hight < j_hight){
            for (int k = 0; k < j_hight - i_hight; ++k) {
                j_parent = j_parent / 2;
            }
        }


        while (i_parent != j_parent){
            i_parent /= 2;
            j_parent /= 2;
        }
        return i_parent;
    }
}


namespace part4_test{
    void test_kmp(){
        int next[12];
        const char* pattern = "ababaaababaa";
        part4::initNext(next, pattern);
        for (int i : next) {
            std::cout << i << " ";
        }


        std::cout << part4::kmp("abcedf","ce");
    }
    void test_page127_5(){
        std::cout << part4::page127_5(8,9) << std::endl;
        std::cout << part4::page127_5(8,10) << std::endl;
        std::cout << part4::page127_5(8,12) << std::endl;
        std::cout << part4::page127_5(8,4) << std::endl;
    }
}


